/*
 * @Author: wwssaabb
 * @Date: 2021-12-06 10:55:42
 * @LastEditTime: 2021-12-06 12:06:01
 * @FilePath: \handwritten-code\algorithm\三数之和.js
 */

/* 
给你一个包含 n 个整数的数组 nums， 判断 nums 中是否存在三个元素 a， b， c， 使得 a + b + c = 0？ 请你找出所有和为 0 且不重复的三元组。
注意： 答案中不可以包含重复的三元组。

示例 1：
输入： nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]

示例 2：
输入： nums = []
输出：[]

示例 3：
输入： nums = [0]
输出：[]

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/3sum
*/

//排序+双指针
var threeSum = function (nums) {
  if (nums.length < 3) return []
  nums = nums.sort((x, y) => x - y)
  let k = 0,
    l = 0,
    sum = 0,
    r = nums.length - 1,
    res = []
  for (k; k < nums.length; k++) {
    l = k + 1
    if (nums > 0) break
    if (nums[k] <= 0 && nums[k] === nums[k - 1]) continue; //k去重
    while (l < r) {
      sum = nums[k] + nums[l] + nums[r]
      if (sum < 0) {
        l++;
        continue
      }
      if (sum > 0) {
        r--;
        continue
      }
      res.push([nums[k], nums[l], nums[r]]);
      while (l < r && nums[l] === nums[++l]); //l去重
      while (l < r && nums[r] === nums[--r]); //r去重
    }
  }
  return res
};

console.log(threeSum([-1, 0, 1, 2, -1, -4])) //[ [ -1, -1, 2 ], [ -1, 0, 1 ] ]
console.log(threeSum([-1, 0, 1, -1, -2, -3, 2, -1, -4])) //[ [ -1, -1, 2 ], [ -1, 0, 1 ] ]
console.log(threeSum([0, 0, 0, 0])) //[ [ -1, -1, 2 ], [ -1, 0, 1 ] ]